package algorithm.stack;

import util.GsonUtil;

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
import java.util.*;

/**
 * leetcode : https://leetcode.com/problems/basic-calculator/description/
 * 224. Basic Calculator
 * Difficulty : Hard
 *
 * 给一个字符表达式，计算结果，
 * 表达式包含 数字，( ) 和 + - 等符号, 数字非负
 * 并且表达式有效
 * @Author Antony
 * @Since 2018/7/30 18:58
 */
public class BasicCalculator {

    public static void main(String[] args) throws ScriptException {
        String s = "(11+2)*4*5*(2+3)";
        System.out.println(calculate(s));
        eval(s);


    }


    public static int eval(String str) throws ScriptException {
        ScriptEngineManager manager = new ScriptEngineManager();
        ScriptEngine scriptEngine = manager.getEngineByName("js");
        Object result = scriptEngine.eval(str);
        System.out.println(result);
        return 0;
    }


    /**
     * 主要有两个步骤：
     * 1、中缀表达式转化为后缀表达式（逆波兰表达式RPN）
     * 2、逆波兰表达式求值
     * @param s
     * @return
     */
    public static int calculate(String s) {
        List<Character> operator = Arrays.asList(new Character[]{'+','-','*','/'}); // 运算符集合
        Map<String, Integer> priMap = new HashMap<>();
        priMap.put("+", 1);
        priMap.put("-", 1);
        priMap.put("*", 2);
        priMap.put("/", 2);
        priMap.put("(", 0);

        LinkedList<String> tokenRPN = new LinkedList<>();                           // RPN表达式
        LinkedList<String> stack = new LinkedList<>();                              // 运算符栈

        Integer num = null;
        for(char c : s.toCharArray()){
            if(Character.isDigit(c)){
                num = num==null ? 0 : num;
                num = num*10 + charToInt(c);
            }else{
                if(num != null){
                    tokenRPN.add(num.toString());
                    num = null;
                }
                    // 如果是运算符
                if(operator.contains(c)){
                    String curr = String.valueOf(c);
                    while(stack.size() > 0 && priMap.get(stack.getFirst()) >= priMap.get(curr)){
                        tokenRPN.add(stack.pop());
                    }
                    stack.push(curr);

                    // 左括号入栈
                }else if('(' == c){
                    stack.push(String.valueOf(c));

                    // 右括号出栈
                }else if(')' == c){
                    inLoop:
                    while(stack.size() > 0){
                        String op = stack.pop();
                        if("(".equals(op)){
                            break inLoop;   // 跳出内循环
                        }
                        tokenRPN.add(op);
                    }
                }
            }
        }

        // 把剩余的数字和运算符压入栈中
        if(num != null){
            tokenRPN.add(num.toString());
        }
        while(stack.size() > 0){
            tokenRPN.add(stack.pop());
        }

        return evalRPN(tokenRPN);
    }

    public static int evalRPN(List<String> tokens){
        Stack<Integer> stack = new Stack<>();
        for(String s : tokens){
            if(s.equals("+")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b+a);
            }else if(s.equals("-")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b-a);
            }else if(s.equals("*")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b*a);
            }else if(s.equals("/")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b/a);
            }else{
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }

    public static int charToInt(char c){
        return c - '0';
    }

}
